Category of relations

In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms.

A morphism (or arrow) R : AB in this category is a relation between the sets A and B, so RA × B.

The composition of two relations R: AB and S: BC is given by:

(a, c) ∈ S o R if (and only if) for some bB, (a, b) ∈ R and (b, c) ∈ S.

Properties

Category Rel has the category of sets Set as a (wide) subcategory, where the arrow (function) f : XY in Set corresponds to the functional relation FX × Y defined by: (x, y) ∈ Ff(x) = y.

Category Rel can be obtained from category Set as the Kleisli category for the monad whose functor corresponds to power set, interpreted as a covariant functor.

The involutary operation of taking the inverse (or converse) of a relation, where (b, a) ∈ R−1 : BA if and only if (a, b) ∈ R : AB, induces a contravariant functor RelopRel that leaves the objects invariant but reverses the arrows and composition. This makes Rel into a dagger category. In fact, Rel is a dagger compact category.

See also